The present invention relates to data processing, and more specifically, to identifying the bit position of a selected instance of a particular bit value within a binary bit string.
Digital electronic systems have several applications in which it is desirable to identify the bit position of a selected (e.g., first, second, third, etc.) instance of a particular bit value (1 or 0) in a binary bit string. Applications range from cryptography to searching for valid or invalid tagged entries in register files. This computation can be performed in software, but software-based implementations can require execution of multiple instructions over a relatively large number of cycles, and the number of processing cycles required to perform the computation generally increases linearly within the length of the bit string. Consequently, software-based implementations are impractical for many applications requiring low latency.
Hardware-based implementations typically sequentially process the bit string to detect the bit position of a selected instance of the particular bit value. This sequential processing requires sequential examination of the bit value of a current bit position and all bit values in preceding bit positions in the bit string. For an N-bit string, an alternative hardware-based implementation evaluates, in parallel, N substrings of different lengths formed by a unique bit position of the bit string (1, 2, . . . , N) and all bits preceding that bit position in the bit string. As the bit position to be evaluated moves further into the bit string, the cone of logic necessary to process the bits of the corresponding substring in parallel can become quite large. Depending on the length of the bit string to be evaluated and the available integrated circuit die area, a conventional parallel processing implementation may be impractical.